An image, especially, a multi-valued image contains a very large volume of information, and upon storing and transmitting such image, the image data size becomes huge. For this reason, storage and transmission of an image use high-efficiency coding that reduces the data size by removing redundancy of an image or changing the contents of an image to a degree at which deterioration of image quality is not visually recognizable.
For example, in JPEG recommended by ISO and ITU-T as an international standard coding scheme of still images, image data is compressed in such a manner that image data is transformed into discrete cosine transform coefficients by computing the DCTs for respective blocks (8 pixels×8 pixels), the respective coefficients are quantized, and the quantized coefficients then undergo entropy coding. Since DCT and quantization are done for respective blocks, a so-called block distortion may be observed at the boundaries of blocks of a decoded image.
On the other hand, JPEG2000 has been examined as a new international standard coding scheme of still images. In JPEG2000, wavelet transformation has been proposed as one of pre-processes to be done before quantization. Since wavelet transformation continuously processes input data unlike the existing JPEG that processes data for respective blocks, deterioration of a decoded image is hard to recognize visually.
FIG. 1 is a block diagram for explaining the operation of a transformation memory 101 and discrete wavelet transformer 102.
FIG. 2A is a block diagram showing the basic arrangement of the discrete wavelet transformer 102. The left diagram in FIG. 2A shows the basic arrangement of a device (discrete wavelet transformer 102) for performing the forward discrete wavelet transformation (to be referred to as DWT hereinafter). Reference symbols H0 denotes a filter having low-pass characteristics; and H1, a filter having high-pass characteristics. The right diagram in FIG. 2A shows the basic arrangement of a device for performing the reverse DWT (inverse DWT). FIG. 5 shows an example of filter coefficients. The following explanation will be given based on forward filter coefficients of a 5×3 filter (five low-frequency taps, 3 high-frequency taps) shown in FIG. 5.
A case will be exemplified below wherein an input image shown in FIG. 2B is sequentially input to the discrete wavelet transformer 102 in turn from the upper left pixel in the main scan direction. Assume that the image size is N×M.
Image data input from the left side in FIG. 2A is filtered by the filter H0 having low-pass characteristics and the filter H1 having high-pass characteristics, the respective results undergo down-sampling to 2:1, and the down-sampling results are finally output as the same number of (N×M) wavelet coefficients as that of input pixels.
In order to execute the aforementioned filtering process in the vertical direction, image data is stored in the transformation memory 101, and is scanned in the horizontal direction while executing the vertical filtering process of M pixels in the vertical direction. As a result, two subbands of low- and high-frequency wavelet coefficients L and H are generated, as shown in FIG. 2C.
In order to further break up these subbands and to obtain wavelet coefficients in the horizontal direction, all the wavelet coefficients L and H are temporarily stored in the transformation memory 101.
The wavelet coefficients stored in the transformation memory 101 are read out in the horizontal direction, N coefficients in the horizontal direction undergo filtering using the filters H0 and H1 by the discrete wavelet transformer 102, and the filtering results are down-sampled to 2:1. As shown in FIG. 2D, LL is obtained by filtering L by H0, and LH is obtained by filtering L by H1. Also, HL is obtained by filtering H by H0, and HH is obtained by filtering H by H1. LL, LH, HL, and HH respectively have a size ((N/2)×(M/2)).
A method called a lifting scheme as a reconstruction method different from the aforementioned discrete wavelet transformation is known. FIG. 3 shows the basic arrangement of a forward lifting scheme, and FIG. 4 shows the basic arrangement of a reverse lifting scheme. In FIGS. 3 and 4, p and u are called lifting coefficients, and FIG. 6 shows an example of lifting coefficients used to generate the same output as the 5×3 filter.
The operation of the forward lifting scheme shown in FIG. 3 will be explained below on the basis of the lifting coefficients (FIG. 6):p=(−1, −1)/2u=(1, 1)/4
X is an input image, and is (X0, X1, X2, X3, X4, X5, . . . ), as shown in FIG. 3. The input image is classified into even- and odd-numbered pixels. Let Xe be the even-numbered pixels of the input image, and Xo be the odd-numbered pixels. The classified pixels are multiplied by the lifting coefficients, and then undergo an addition process, thus being converted into low- and high-frequency coefficients. More specifically, this process is described by:(High-frequency coefficient) X′o=Xo+p·Xe(Low-frequency coefficient) X′e =Xe+u·X′owhere X′o and X′e are respectively the low- and high-frequency coefficients. Note that k in FIG. 3 normalizes wavelet coefficients, but a detailed description thereof will be omitted since it does not directly concern the contents to be explained here.
Generation of pixels as the output of the reverse lifting scheme shown in FIG. 4 is described by:(Even-numbered pixel) Xe=X′e−u·X′o(Odd-numbered pixel) Xo=X′o−p·Xe
As can be seen from FIGS. 3 and 4, if the filter configuration changes, lifting coefficients and pixels to be processed differ, but the forward and reverse transformation processes of coefficients can be similarly done.
When this lifting scheme is used, if quantization is not made (or quantization using quantization step=1 is made), reversible transformation can be achieved, i.e., data reclaimed after compression encoding and decoding becomes the same as original data as long as quantized information is free from any loss. In JPEG2000, reversible transformation is implemented by adopting the lifting scheme.
As another feature of the lifting scheme, the arithmetic volume required for the filter process can be reduced, and the lifting scheme is also used in a 9×7 filter (9 low-frequency taps, 7 high-frequency taps) of JPEG2000.
However, the arithmetic volume of the filter process can be reduced using the lifting scheme when the filter direction agrees with the scan direction of the process, i.e., when the horizontal filter process is done while scanning image data in the horizontal direction. This is because intermediate results computed for the purpose of outputting high- and low-frequency transform coefficients at the previous sampling point can be re-used at the next sample point.
The process in the lifting scheme will be explained below using a lifting lattice shown in FIG. 7.
A case will be examined below wherein a horizontal sequence of pixels X0, X1, X2, X3, X4, . . . undergoes horizontal DWT transformation, and is scanned to the right. Assume that transform coefficients s4 and d5 corresponding to positions indicated by black dots have already been obtained.
s4 is the low-frequency transform coefficient of a 9×7 DWT filter, and d5 is the high-frequency transform coefficient. To obtain these coefficients s4 and d5, eight transform data indicated by gray dots in FIG. 7 also have already been calculated. For example, d′1 as one transform data is calculated by:d′1=X1+α·(X0+X2)
Other transform data are calculated using substantially the same arithmetic formulas except for inputs, multiplication coefficients, and the like. In this connection, in JPEG2000, coefficients are defined as follows:
α=−1.586134342
β=−0.052980118
γ=0.882911075
δ=0.443506852
In FIG. 7, when data at all gray dots have already been calculated, the next transform coefficients to be calculated are s6 and d7. When the previously calculated transform data and transform coefficients are re-used, the number of transform data to be newly calculated is two (d′9 and s′8), and the number of transform coefficients to be newly calculated is also two (s6 and d7), i.e., a total of four transform data and coefficients need only be calculated. Only two calculations are required per transform coefficient.
The contents of one calculation include one addition for adding the two end inputs of three inputs, one multiplication for multiplying the sum by the coefficient α or β, γ, δ, or the like, and one addition (second addition) for adding the product to the central input. This calculation will be referred to as a lattice point computation hereinafter.
Three transform coefficients/data d5, s′6, and d′7 are to be re-used, and as can be easily understood from the lifting lattice in FIG. 7, the calculated values can be easily re-used by only holding them in registers without any special control.
Conventionally, when filter processes such as wavelet transformation and the like are required as partial processes of a codec, two different filter processors, i.e., a filter processor for forward transformation and that for reverse transformation must be prepared, and the circuit scale consequently increases. The filter configuration is not suitable for hierarchical design, the circuit structure is complicated, and the times required for development and debugging are long, resulting an increase in cost of a product that incorporates that function.
The present invention has been made in consideration of the aforementioned problems, and has as its object to suppress an increase in circuit scale and to simplify the circuit structure by executing filter processes using a plurality of arithmetic units that make multiplication and addition.
Wavelet transformation used in JPEG2000 allows efficient transformation with a smaller arithmetic volume if it is processed by a method called a lifting scheme.
FIG. 30 shows the signal flow of the forward lifting scheme, and FIG. 31 shows the signal flow of the reverse lifting scheme. In FIGS. 30 and 31, α, β, γ, and δ are called lifting coefficients. The operation of FIG. 30 will be described below.
Input pixels are expressed in turn by X0, X1, X2, X3, X4, X5, . . . . The input pixels are classified into even- and odd-numbered pixel sequences by a classification unit 5201, pixels X0, X2, X4, . . . with even-numbered suffices are output to the upper side of the unit, and pixels X1, X3, X5, . . . with odd-numbered suffices are output to the lower side of the unit.
In a lifting process of the first stage, the even-numbered pixel sequence is multiplied by the lifting coefficient: α, and two successive products are added to a pixel in the odd-numbered pixel sequence located at the center of these two pixels.
This process can be generally described by:D2n+1=X2n+1+α·X2n+α·X2n+2  (1)
In a lifting process of the second stage, a newly obtained odd-numbered pixel sequence (D1, D3, D5, . . . ) is multiplied by the lifting coefficient: β, and two successive products are added to a pixel in the even-numbered pixel sequence located at the center of these two pixels.
This process can be generally described by:E2n+2=X2n+2+β·D2n+1+β·D2n+3  (2)
In a lifting process of the third stage, the same process as in the first stage is done using the lifting coefficient: γ. In a lifting process of the fourth stage, the same process as in the second stage is done using the lifting coefficient: δ. The lifting process contents of the third and fourth stages are described by:H2n+1=D2n+1+γ·E2n+γ·E2n+2  (3)L2n+1=E2n+2+δ·H2n+1+δ·H2n+3  (4)
In FIG. 30, K normalizes wavelet coefficients, but a detailed description thereof will be omitted since it is not essential to the present invention.
If the normalization process is ignored, Hn and Ln obtained by the lifting processes of the third and fourth stages respectively correspond to high- and low-frequency transform coefficients.
The signal flow of the reverse lifting scheme shown in FIG. 31 will be briefly explained below. After inverse coefficients are multiplied in correspondence with the normalization process in the forward lifting scheme, lifting processes of four stages are done. The processing contents of the respective stages are described by:(First stage) E2n+2=L2n+2−δ·H2n+1−δ·H2n+3  (5)(Second stage) D2n+1=H2n+1−γ·E2n−γ·E2n+2  (6)(Third stage) X2n+2=E2n+2−β·D2n+1−β·D2n+3  (7)(Fourth stage) X2n+1=D2n+1−α·X2n−α·X2n+2  (8)
Equations (5), (6), (7), and (8) are obtained by transposing the terms of equations (4), (3), (2), and (1), respectively.
The lifting lattice structures shown in FIGS. 32 and 33 express the lifting scheme processes shown in FIGS. 30 and 31 from another viewpoint. In FIGS. 32 and 33, □ represents input data, ∘ represents lattice points (or lattice point data arithmetic units), and arrows extending from ∘ indicate the flows of lattice point data. These figures illustrate the basic processes (the processes of equations (1) to (8)) in the lifting scheme and new data obtained by these processes in correspondence with one lattice point.
In the forward lifting lattice structure shown in FIG. 32, one lattice point data is calculated using one of equations (1) to (4). In the reverse lifting lattice structure shown in FIG. 33, one lattice point data is calculated using one of equations (5) to (8).
Since a filter process such as wavelet transformation or the like requires many data to obtain one output, a region outside an image is referred to upon calculating a filter output for pixels at the boundary of the image. However, there is no data in such external region.
Hence, a process different from a normal process (to be referred to as a boundary process hereinafter) is required at the boundary of the image. As a simplest method, data of the boundary are continuously copied to and written in an external region to be referred to in advance.
In wavelet transformation in JPEG2000, internal data are arranged in the external region by a method of replicating internal data to have boundary data as the center.
FIG. 34 shows an example. In FIG. 34, ▪ represents boundary input data, and other symbols are the same as those in FIG. 32.
Outside (on the left side of) X0 as left boundary input data, data X1, X2, X3, and X4 inside the boundary are replicated and arranged. Outside (on the right side of) X5 as right boundary input data, data X4, X3, and X2 inside the boundary are replicated and arranged.
In this way, when data are prepared in advance in a region outside the boundary, wavelet transform coefficients corresponding to all source data can be computed without any exceptional process.
The aforementioned method of preparing data in a region outside the boundary suffers the following problems.                A process for preparing data in a region outside the boundary is additionally required.        An extra storage area for storing replicated data outside the boundary is required.        
The present invention has been made in consideration of the above problems, and has as its object to provide a filter process apparatus and its control method, a program, and a storage medium, which can simplify a structure since data outside a boundary need not be generated by a pre-process even when data to be processed is located outside the boundary of image data.
A wavelet transformation filter process using the lifting scheme will be described below.
Wavelet transformation used in JPEG2000 allows efficient transformation with a smaller arithmetic volume if it is processed by a method called a lifting scheme.
FIG. 30 shows the signal flow of the forward lifting scheme, and FIG. 31 shows the signal flow of the reverse lifting scheme. FIGS. 30 and 31 show the signal flows when data of 9 taps are used upon computing low-frequency wavelet transform coefficients, and data of 7 taps are used upon computing high-frequency wavelet transform coefficients. In FIGS. 30 and 31, α, β, γ, and δ are called lifting coefficients.
The operation of FIG. 30 will be described below.
Input pixels are expressed in turn by X0, X1, X2, X3, X4, X5, . . . , Xn. The input pixels are classified into even- and odd-numbered pixel sequences by a classification unit 5201, pixels X0, X2, X4, . . . , X2n with even-numbered suffices are output to the upper side of the unit, and pixels X1, X3, X5, . . . , X2n+1 with odd-numbered suffices are output to the lower side of the unit.
In a lifting process of the first stage, the even-numbered pixel sequence is multiplied by the lifting coefficient: α, and two successive products are added to a pixel in the odd-numbered pixel sequence located at the center of these two pixels.
This process can be generally described by:D2n+1=X2n+1+α·X2n+α·X2n+2  (9)
In a lifting process of the second stage, a newly obtained odd-numbered pixel sequence (D1, D3, D5, . . . , D2n+1) is multiplied by the lifting coefficient: β, and two successive products are added to a pixel in the even-numbered pixel sequence located at the center of these two pixels.
This process can be generally described by:E2n+2=X2n+2+β·D2n+1+β·D2n+3  (10)In a lifting process of the third stage, the same process as in the first stage is done using the lifting coefficient: γ. In a lifting process of the fourth stage, the same process as in the second stage is done using the lifting coefficient: δ. The lifting process contents of the third and fourth stages are generally described by:H2n+1=D2n+1+γ·E2n+γ·E2n+2  (11)L2n+1=E2n+2+δ·H2n+1+δ·H2n+3  (12)
In FIG. 30, K normalizes wavelet coefficients, but a detailed description thereof will be omitted since it is not essential to the present invention.
If the normalization process is ignored, Hn and Ln obtained by the lifting processes of the third and fourth stages respectively correspond to high- and low-frequency transform coefficients.
The signal flow of the reverse lifting scheme shown in FIG. 31 will be briefly explained below. After inverse coefficients are multiplied in correspondence with the normalization process in the forward lifting scheme, lifting processes of four stages are done. The processing contents of the respective stages are generally described by:(First stage) E2n+2=L2n+2−δ·H2n+1−δ·H2n+3  (13)(Second stage) D2n+1=H2n+1−γ·E2n−γ·E2n+2  (14)(Third stage) X2n+2=E2n+2−β·D2n+1−βD2n+3  (15)(Fourth stage) X2n+1=D2n+1 −α·X2n−·X2n+2  (16)
Equations (13) to (16) are obtained by transposing the terms of equations (12) to (9), respectively.
The wavelet transformation filter process using the lifting scheme has been explained. A wavelet transformation filter process that combines recursive arithmetic operations with the lifting scheme will be explained below.
The lifting lattice structures shown in FIGS. 32 and 33 express the lifting scheme processes shown in FIGS. 30 and 31 from another viewpoint. In FIGS. 32 and 33, □ represents input data, ∘ represents lattice points (or lattice point data arithmetic units), and arrows extending from ∘ indicate the flows of lattice point data. These figures illustrate the basic processes (the processes of equations (9) to (16)) in the lifting scheme and new data obtained by these processes in correspondence with one lattice point.
In the forward lifting lattice structure shown in FIG. 32, one lattice point data is calculated using one of equations (9) to (12). In the reverse lifting lattice structure shown in FIG. 33, one lattice point data is calculated using one of equations (13) to (16).
By observing the lifting lattice structure, the dependence among input data and lattice point data is manifest. For example, upon calculating L4 as transform output data, nine input data: X0 to X8 are required. Also, as can be seen from this structure, L4 can be calculated from only three lattice point data: H3, E4, and H5.
When L4 and H5 have been calculated and output, four data X8, D7, E6, and H5 can be left. From these four data and new input data X9 and X10, four lattice point data can be calculated in the order of D9, E8, H7, and L6. L6 and H7 are output as transform data, and four data X10, D9, E8, and H7 are left and re-used in the next calculation, thus allowing efficient arithmetic processes.
In order to efficiently execute the arithmetic processes, pairs of pixel data with even- and odd-numbered suffices from the head of the sequences must be processed as units. In the above description, since the pairs of input pixel data start from an odd-numbered suffix, pixel data with an even-numbered suffix at the head is odd.
In horizontal wavelet transformation, only one head pixel is odd. However, in vertical wavelet transformation, data for one head line become odd. In addition, since the vertical size of most of image data is specified by an even number, last one line becomes odd.
In case of hardware processing, since the time required for processing a pair of lines is the same as that required for processing the head one line, one odd line at each of the head and end of an image has poor processing efficiency.
As described above, when efficient arithmetic processes are executed by saving the lifting processing results and re-using them, data for two lines in the middle of a data stream can be simultaneously processed. However, in an image having an even-numbered size, only the head and last lines must be solely processed, resulting in poor efficiency.
The present invention has been made to solve the aforementioned problems, and has as its object to provide a filter processing apparatus and its control method, a program, and a storage medium, which can efficiently execute wavelet transformation.